|
An operator precedence grammar is a kind of grammar for formal languages. Technically, an operator precedence grammar is a context-free grammar that has the property (among others〔Aho, Sethi & Ullman 1988, p. 203.〕) that no production has either an empty right-hand side or two adjacent nonterminals in its right-hand side. These properties allow precedence relations to be defined between the terminals of the grammar. A parser that exploits these relations is considerably simpler than more general-purpose parsers such as LALR parsers. Operator-precedence parsers can be constructed for a large class of context-free grammars. == Precedence Relations == Operator precedence grammars rely on the following three precedence relations between the terminals:〔Aho, Sethi & Ullman 1988, pp. 203-204.〕 These operator precedence relations allow to delimit the handles in the right sentential forms: <• marks the left end, =• appears in the interior of the handle, and •> marks the right end. Contrary to other shift-reduce parsers, all nonterminals are considered equal for the purpose of identifying handles.〔Aho, Sethi & Ullman 1988, pp. 205-206.〕 The relations do not have the same properties as their un-dotted counterparts; e. g. a =• b does not generally imply b =• a, and b •> a does not follow from a <• b. Furthermore, a =• a does not generally hold, and a •> a is possible. Let us assume that between the terminals ai and ai+1 there is always exactly one precedence relation. Suppose that $ is the end of the string. Then for all terminals b we define: $ <• b and b •> $. If we remove all nonterminals and place the correct precedence relation: <•, =•, •> between the remaining terminals, there remain strings that can be analyzed by an easily developed bottom-up parser. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Operator-precedence grammar」の詳細全文を読む スポンサード リンク
|